package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1027. 最长等差数列
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/21 21:20
 */
public class LongestArithSeqLength {

    public static void main(String[] args) {
        LongestArithSeqLength test = new LongestArithSeqLength();

        // 4
//        int[] arr = {3,6,9,12};

        // 3
        int[] arr = {9, 4, 7, 2, 10};

        // 4
//        int[] arr = {20,1,15,3,10,5,8};

        int i = test.longestArithSeqLength(arr);
        System.out.println(i);
    }

    public int longestArithSeqLength(int[] nums) {
        int length = nums.length;
        Map<Integer, Integer>[] arr = new HashMap[length];
        int max = 0;
        arr[0] = new HashMap<>();
        for (int i = 1; i < length; i++) {
            int v = nums[i];
            Map<Integer, Integer> map = new HashMap<>();
            arr[i] = map;
            for (int j = i - 1; j >= 0; j--) {
                int k = v - nums[j];
                int c = arr[j].getOrDefault(k, 1) + 1;
                max = Math.max(max, c);
                map.merge(k, c, (a, b) -> Math.max(b, a));
            }
        }
        return max;
    }

}
